// 前缀和 + 动态规划 + 哈希表
// 本质上是一个动态规划的思想，关键步骤如下：
// 1.确定状态表示
// 2.推导动态转移方程
// 3.初始化
// 4.确定填表顺序
// 5.确定返回值

// 例题 7：
// 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
//
//        示例 1:
//
//        输入: nums = [0,1]
//        输出: 2
//        说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
//        示例 2:
//
//        输入: nums = [0,1,0]
//        输出: 2
//        说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
//
//        提示：
//
//        1 <= nums.length <= 105
//        nums[i] 不是 0 就是 1

// 解题思路：
// 本题乍一看是一个找子数组个数的题目，首先就会想到用滑动窗口的办法
// 再仔细一看，发现数组里面的数值有正有0，数据本身不具备单调性，因此无法用滑动窗口解题

// 进而利用动态规划的思想进行解题，直接求解比较复杂，需要先把数组中值为 0 的元素改成 -1，
// 这样问题就转化成了在数组中找和为 0 的子数组的最大长度，题目就类似例题 5；
// 首先需要定义状态表示 dp[i]：以 i 位置为结尾和为 0 的所有子数组的最大长度，
// 定义完状态表示后，我们发现不好推导状态转移方程
// 原因是 dp[i] 和 dp[i - 1] 没有直接的关系，dp[i] 和前面的所有 dp[j] 有关系
// 因此想到使用前缀和的办法：dp[i] = 前缀和为 sum 的所有子数组中长度最短的子数组的长度，这也同时符合“正难则反”的思想
// 统计前缀和最好的数据结构还是哈希表，因为哈希表查询的时间复杂度为 O(1)
// 哈希表中存的内容是前缀和及其下标，统计好下标，才能方便求长度，最终求出长度后，要取最大值
// 因此，每计算一次前缀和，首先需要判断哈希表中有没有存这个前缀和，如果存了，就要算一下和为 0 子数组的最大长度
// 如果没存，就表示前面不存在这样的前缀和，就要把前缀和及其下标放进哈希表中

import java.util.HashMap;
import java.util.Map;

public class FindMaxLength {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, -1);
        int sum = 0;
        int ret = 0;
        for(int i = 0; i < n; i++){
            sum += (nums[i] == 0) ? -1 : 1;
            if(hash.containsKey(sum)) ret = Math.max(ret, i - hash.get(sum));
            else hash.put(sum, i);
        }
        return ret;
    }
}
